/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 希尔排序（Shell Sort）是插入排序的一种，也是直接插入排序的更高效的改进版本，希尔排序充分利用了插入排序的两个特点：
 * <p>
 * 1）当数据规模小的时候非常高效。
 * <p>
 * 2）当给定数据已经有序时的时间复杂度为O(n)。
 * <p>
 * 所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停地合并小块，直到最后一个小块。
 * <p>
 * 这里每次分成若干个小块是通过“增量”来控制的，开始的时候增量较大，接近n/2，从而使得分割出来接近n/2个小块，逐渐的减小“增量”，最终减小到1。
 * <p>
 * 希尔排序时间复杂度为 O(n^1.3)
 *
 * <a href="https://www.dotcpp.com/course/899">课程地址</a> *
 *
 * @author lizhixing
 */
public class ShellSort {

  public static void main(String[] args) {
    int[] data = new int[] { 4, 6, 1, 9, 5, 8 };
    print(data);
    shellSort(data);
    print(data);
  }

  public static void shellSort(int[] data) {
    // 计算出最大的h值
    int h = 1;
    while (h <= data.length / 3) {
      h = h * 3 + 1;
    }
    while (h > 0) {
      for (int i = h; i < data.length; i += h) {
        if (data[i] < data[i - h]) {
          int tmp = data[i];
          int j = i - h;
          while (j >= 0 && data[j] > tmp) {
            data[j + h] = data[j];
            j -= h;
          }
          data[j + h] = tmp;
        }
      }
      // 计算出下一个h值
      h = (h - 1) / 3;
    }
  }

  public static void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }
}
